package bfs;

import java.util.LinkedList;
import java.util.Queue;
public class 腐烂的橘子 {
    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        Queue<int[]> queue = new LinkedList<>();
        // 记录新鲜橘子的数量
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]==1)
                    count++;
                else if (grid[i][j]==2)
                    queue.offer(new int[]{i,j});
            }
        }
        //分钟数
        int round = 0;
        while (count>0 && !queue.isEmpty()){
            round++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] poll = queue.poll();
                for (int j = 0; j < 4; j++) {
                    int x = poll[0]+dirs[j][0];
                    int y = poll[1]+dirs[j][1];
                    if (x>=0 && x<m && y>=0 && y<n && grid[x][y]==1){
                        grid[x][y] = 2;
                        count--;
                        queue.offer(new int[]{x,y});
                    }
                }
            }
        }
        //说明还有新鲜橘子
        if (count!=0)
            return -1;
        return round;
    }
}
